package concurrent.mergesort;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

/**
 *
 * @author Iaroslav_Mazai
 */
public class MergeSortUtils {

	public static List<Integer> generateRandomList(Integer size, Integer valueCap) {
		List<Integer> result = new ArrayList<>();
		Random random = new Random();

		for (int i = 0; i < size; i++) {
			result.add(random.nextInt(valueCap));
		}

		return result;
	}

	public static List<Object> merge(List<Object> left, List<Object> right) {
		List result = new ArrayList<Object>();
		ListIterator leftIterator = left.listIterator();
		ListIterator rightIterator = right.listIterator();
//		Iterator resultIterator = result.iterator();

		while ((leftIterator.hasNext()) || (rightIterator.hasNext())) {
			// Special case when left list has ended
			if (!leftIterator.hasNext() && rightIterator.hasNext()) {
				result.add(rightIterator.next());
				continue;
			}

			// Special case when right list has ended
			if (!rightIterator.hasNext() && leftIterator.hasNext()) {
				result.add(leftIterator.next());
				continue;
			}

			// Now the common case when nothing did not end =)
			Object leftElement = leftIterator.next();
			Object rightElement = rightIterator.next();
			if (((Comparable) leftElement).compareTo(rightElement) > 0) {
				result.add(rightElement);
				leftIterator.previous();
			} else {
				result.add(leftElement);
				rightIterator.previous();
			}
		}

		return result;
	}
}
